#include "linklist.h"

// 初始化一条空单链表（带头结点）
struct listnode *init_list(void)
{
    struct listnode *head = malloc(sizeof(struct listnode));
    if(head != NULL)
    {
        head->next = NULL;
    }
    return head;
}

struct listnode *newnode(int num)
{
    struct listnode *new = malloc(sizeof(struct listnode));
    if(new != NULL)
    {
        new->data = num;
        new->next = NULL;
    }
    return new;
}

// 添加节点（头插法）
bool add_list(struct listnode *head, int num)
{
    // 申请新节点
    struct listnode *new = newnode(num);

    // 插入链表头
    new->next = head->next;
    head->next = new; // 将新节点的地址放入head->next
    return true;
}


// 添加节点（尾插法）
bool add_list_tail(struct listnode *head, int num)
{
    // 申请新节点
    struct listnode *new = newnode(num);

    // 插入链表尾
    struct listnode *p;
    for(p=head; p->next!=NULL; p=p->next);
    p->next = new;

    return true;
}

// 删除指定数据的节点
struct listnode *remove_node(struct listnode *head, int num)
{
    // 1. 试图找到要删除的节点
    struct listnode *p, *q;
    for(p=head->next; p!=NULL; p=p->next)
    {
        if(p->data == num)
        {
            // 2
            for(q=head; q->next!=p; q=q->next);
            // 3
            q->next = p->next;
            // 4
            p->next = NULL;
            // 5
            return p;
        }
    }

    return NULL;
}

// 删除指定节点p
struct listnode *del_list(struct listnode *head, struct listnode *p)
{
    // 找到p前面的节点q
    struct listnode *q;
    for(q=head; q->next!=p; q=q->next);
    q->next = p->next;
    p->next = NULL;
    return p;
}

// 从头到尾遍历链表
void show(struct listnode *head)
{
    for(struct listnode *p=head->next; p!= NULL; p=p->next)
    {
        printf("%d\t", p->data);
    }
    printf("\n");
}

// 彻底删除链表（包括头结点）
struct listnode *destroy(struct listnode *head)
{
    destroy_init(head);
    free(head);
    return NULL;
}

struct listnode *destroy_init(struct listnode *head)
{
    if(head == NULL)
        return NULL;

    // n用来指向p的下一个节点，防止p被释放掉之后找不到
    for(struct listnode *p=head->next, *n; p!=NULL; p=n)
    {
        n = p->next;
        p = del_list(head, p);
        free(p);
    }
    return head;
}